package arithmetic.ok_coin;

import java.util.Arrays;

/**
 * Created by jiangfeng on 2018/3/26. ע�� �������һ������ͬ���ӽ�С���������룬����С�����뽫���������ľ��١� ʼ�տ���С�����ĵ�ֵ������10.9 - > 10�� ʾ�� ���룺 num = 4 secretCode : 1 3 5 7 ����� 5 ���ͣ� ��1����N�����ٵ�С�����= 8�������ų�7 ��2�������¼���N-1�����ٵ�С����롣 С�����= 4����ֵ���� ���ԣ��ų�3����Ϊ3 <5�� ��3�������¼���N-2�����ٵ�С����롣 С�����= 3�����ԣ��ų�1����Ϊ1 <5�� ���ԣ������5��
 *
 * 3, [1, 3, 27]    27
 */
public class Main3 {

    public static void main(String[] args) {
        //int a = secretCodeOfTerrorist(3,new int[]{1,3,27});
//        System.out.println(a);
        int b = secretCodeOfTerrorist(3, new int[]{1, 3, 5, 7});
        System.out.println(b);
    }

    public static int secretCodeOfTerrorist(int num, int[] secretCode) {
        //  �ȴ�С��������
        Arrays.sort(secretCode);
        // WRITE YOUR CODE HERE
        for (int i = secretCode.length - 1; i > 0; i--) {
            // ������Ե�code
            int code = calcCode(secretCode, i);
            // �ҵ����Եף����޳�
            findNoBlack(secretCode, code, i);
        }
        return secretCode[0];
    }


    public static int calcCode(int[] secretCode, int endIndex) {
        int code = 0;
        for (int i = 0; i <= endIndex; i++) {
            code += secretCode[i];
        }
        return code / 2;
    }

    public static void findNoBlack(int[] secretCode, int jcode, int endIndex) {
        int noblackIndex = endIndex;
        int min = secretCode[endIndex];
        for (int i = endIndex; i >= 0; i--) {
            int a = secretCode[i];
            // �˴�Ӧ��д=����ΪҪ���code �Ĳ��С�
            if (min >= Math.abs(a - jcode)) {
                min = Math.abs(a - jcode);
                noblackIndex = i;
            }
        }
        // �����������
        int temp = secretCode[noblackIndex];
        secretCode[noblackIndex] = secretCode[endIndex];
        secretCode[endIndex] = temp;
    }

    // ���Ż�һ�£�����Ż��������⡣˼·������������� ��һ������jcode��ߵ�ֵ�ͽ���ѭ��������������
    public static void findNoBlack2(int[] secretCode, int jcode, int endIndex) {
        int noblackIndex = endIndex;
        int min = Integer.MAX_VALUE;
        for (int i = endIndex; i >= 0; i--) {
            int temp = secretCode[i] - jcode;
            // �˴�Ӧ��д=����ΪҪ���code �Ĳ��С�
            if (temp >= 0) {
                if (min > temp) {
                    min = temp;
                    noblackIndex = i;
                }
            } else {
                if (min > -temp) {
                    // min=-temp; ��Ϊ�Ź�˳������߻�Խ��Խ��
                    noblackIndex = i;
                    break;
                }
            }
        }
        // �����������
        int temp = secretCode[noblackIndex];
        secretCode[noblackIndex] = secretCode[endIndex];
        secretCode[endIndex] = temp;
    }


}
